package org.kk.array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 请设计一个高效算法，判断数组中是否有重复值。必须保证额外空间复杂度为O(1)。
 * 给定一个int数组A及它的大小n，请返回它是否有重复值。
 * @author kk
 * @Date 2021/1/29
 */
public class CheckDuplicate {
    public static void main(String[] args) {
        int[] nums = {1,2,3,6,4,5,2,6,4};
        System.out.println(Arrays.toString(nums));
        List<Integer> result = checkDuplicate(nums);
        System.out.println(result);
        System.out.println(Arrays.toString(nums));
        int repeatNumber = findRepeatNumber(nums);
        System.out.println(repeatNumber);
    }
    /**
     * 判断数组中是否有重复数组并返回
     * 要求 空间复杂度为O(1)
     */
    public static List<Integer> checkDuplicate(int[] nums){
        List<Integer> result = new ArrayList<>();
        if(nums == null || nums.length == 0) return result;
        for (int i = 0; i < nums.length; i++) {
            if(i == nums[i]) continue;
            while(i != nums[i]){
                if(nums[i] == nums[nums[i]]){
                    result.add(nums[i]);
                    break;
                }
                int temp = nums[i];
                nums[i] = nums[temp];
                nums[temp] = temp;
            }
        }
        return result;
    }

    /**
     * 我们可以构建这个一个特殊的哈希表，下标0~n-1依次对应数值0~n-1有没有出现过，如果数字x第一次出现，那么下标x 的位置的元素应该为该位置的相反值，
     * 标识这个数字x出现过，当我们下一次再遇到x，判断一下下标x的值是否<0，如果是的话表示之前已经访问过，我们就找到了这个重复的数 因为题意表明一定有重复的数字
     * 所以如果在前面都没有返回的话 说明重复的数字就是0 直接最后返回0就好了
     */
    public static int findRepeatNumber(int[] nums) {
        for(int i = 0;i < nums.length ; i++){
            nums[i] = nums[i]+1;
        }
        int out = 0;
        for (int i = 0; i < nums.length ; i++) {
            //nums[i]可能为负(为负是因为这个下标对应的元素出现过了)，所以应该用绝对值表示
            int index = Math.abs(nums[i]);
            if (nums[index-1]<0){
                out = index-1;
                break;
            }
            nums[index-1] *= (-1) ;
        }
        return out;
    }
}
